#include <stdio.h>
#include "diskBTree.h"
/* B树表示m-阶平衡树（balance），而AVL树是2阶平衡树，B树是更平衡的树，他所有叶子节点都在同一层
 * 插入需要分裂，不用旋转
 * *
 * 一个m阶B树需要满足：
 * - 树中每个节点最多含有m个孩子
 * - 除根节点和叶节点以外，其它每个节点至少有ceil(m/2)个孩子，表示向上取整，即至少包含一半的孩子
 * - 除根节点之外的节点的关键字个数n必须满足 ceil(m/2) <= n <= m - 1
 * ================================= 插入操作 ====================================
 * - 如果叶子节点空间足够，即该节点的key值个数小于m-1，则直接插入在叶子节点的左边或右边；
 * - 如果空间满了以致没有足够的空间去添加新的元素，即该节点的key值个数已经有m个，则需要将该节点进行“分裂”
 * 		将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父节点中，
 * 		而且当节点中元素向右移动了，相关的指针也需要右移；
 * - 此外，如果在上述中间关键字上移到父节点的过程中，导致根节点空间满了，那么根节点也要进行分裂操作，
 * 		这样原来的根节点中的中间关键字元素向上移动到新的根节点中，因此导致树的高度增加一层。
 * ================================== 删除操作 ===================================
 * 首先查找B树中要删除的元素，若元素存在，则进行删除，删除该元素后，需要判断该元素是否有左右孩子节点
 * 1）如果有，则上移孩子节点中相近元素（左孩子中最右边的节点或者右孩子中最左边的节点）到父节点中去。
 * 2）如果没有，直接删除
 * 删除元素，然后进行元素移动之后，如果节点关键字数目不满足条件（小于ceil(m/2) - 1），
 * 		则需要看其相邻的兄弟节点是否丰满（大于ceil(m/2) - 1）
 * 如果其相邻兄弟都刚脱贫，即借了之后其节点数目小于ceil(m/2) - 1，则该节点与其相邻的某一兄弟节点进行“合并”成一个节点
 * ================================== B树的优势 ==================================
 * 文件索引系统中应用，数据库的索引
 * 数据量非常大 ==》存储磁盘上，会为数据创建索引，加速搜索
 * 1）解决更少的磁盘I/O
 * 2）更快的搜索算法
 * ======================= B+树更适合操作系统的文件索引和数据库索引的原因 ===============
 * B+树的磁盘读写代价更低，B+树的内部节点没有指向关键字具体信息的指针，因此内部节点相对B树更小。
 * 		如果把所有同一内部节点的关键字放在同一块磁盘中，盘块所能容纳的关键字数量也就越多，
 * 		一次性读入内存中的需要查找的关键字也就越多，相对IO读写次数降低。
 * 举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。
 * 		一棵9阶B-tree(一结点最多8个关键字)的内部结点需要2个盘块。而B+树内部结点只需要1个盘快。
 * 		当需要把内部结点读入内存中的时候，B树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)
 * B+树的查询效率更加稳定
 * 		由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。
 * 		所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
 * */
int main() {
	DiskBTree *bTree = initDiskBTree();

	insertKey(bTree, 8);
	insertKey(bTree, 9);
	insertKey(bTree, 10);
	insertKey(bTree, 11);
	insertKey(bTree, 15);
	insertKey(bTree, 16);
	insertKey(bTree, 17);
	insertKey(bTree, 18);
	insertKey(bTree, 20);
	insertKey(bTree, 23);
	PrintBTree(bTree->root,1);

	printf("====================\n");
	deleteKey(bTree, 15);
	PrintBTree(bTree->root,1);
	orderTravelBTree(bTree);

	Result res;
	searchBTree(bTree, 15, &res);
	if (res.tag) {
		printf("find: %d\n", res.ptr->key[res.pos]);
	} else {
		printf("Not find!\n");
	}
	releaseDiskBTree(bTree);
	return 0;
}
